package leetcode_1001_1100;

import java.util.*;

public class LeeCode_1091 {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();
        System.out.println(shortestPathBinaryMatrix(new int[][]{{0, 0, 0}, {1, 1, 0}, {1, 1, 0}}));
        System.out.println(shortestPathBinaryMatrix(new int[][]{{0, 1}, {1, 0}}));
    }

    private static int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1)
            return -1;
        int n = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, 0});
        grid[0][0] = 1;
        int count = 0;
        int[][] dis = new int[][]{{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] poll = queue.poll();
                int x = poll[0], y = poll[1];
                if (x == n - 1 && y == n - 1) {
                    return count + 1;
                }
                for (int[] di : dis) {
                    int x0 = x + di[0];
                    int y0 = y + di[1];
                    if (x0 < 0 || x0 >= n || y0 < 0 || y0 >= n || grid[x0][y0] == 1) {
                        continue;
                    }
                    queue.offer(new int[]{x0, y0});
                    grid[x0][y0] = 1;
                }
            }
            count++;
        }
        return -1;
    }

    public static int shortestPathBinaryMatrix2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        // 如果起点就阻塞那就玩完啦
        if (grid[0][0] == 1) {
            return -1;
        }
        //定义 8个方向
        int[][] dir = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
        int m = grid.length;
        int n = grid[0].length;
        //bfs的老套路 来个队列
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});   //把起点扔进去
        grid[0][0] = 1;        // 把起点标记为阻塞
        int path = 1;     // 层数

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];

                //能放进队列里的都是为0可以走的（这一点在后面保证了）
                // 如果等于终点则返回
                if (x == m - 1 && y == n - 1) {    //
                    return path;
                }

                //开始八个方向的判断
                for (int[] d : dir) {
                    int x1 = x + d[0];
                    int y1 = y + d[1];
                    //这里开始过滤
                    if (x1 < 0 || x1 >= m || y1 < 0 || y1 >= m || grid[x1][y1] == 1) {
                        continue;
                    }
                    //把在数组范围内 并且为0不阻塞的放入队列中
                    queue.add(new int[]{x1, y1});
                    grid[x1][y1] = 1; // 标记
                }
            }
            path++;  //遍历完一层 这时候要 ++啦
        }
        return -1;
    }
}
